jupyter. Другие формы (листочки, сканы тетрадки и пр.) не принимаются :(.pdf, .ipynb, .zip, .rar) боту в telegram: https://t.me/optimization_hw_bot



Выход: 3d модель, подобранная с помощью алгоритмов выпуклой оптимизации и корректно поставленной задачи оптимизации.

Решение $x^*$ доставляет наименьшее значение функции $f_0(x)$ среди всех $x$, удовлетворяющих ограничениям
$\text{extr}\left(x_1 + x_2\right)$ при условии $x_1^2 + 4x_2^2 \le 4$
Решение:
import plotly
import plotly.plotly as py
import plotly.graph_objs as go
plotly.offline.init_notebook_mode(connected=True)
import numpy as np
r = np.linspace(0,1,240) # radius
phi = np.linspace(0, 2*np.pi, 240) # angle
r, phi = np.meshgrid(r, phi) # computational grid
x1 = 2 * r * np.cos(phi) # parametrization
x2 = r * np.sin(phi)
z = np.zeros((240,240))
budget_set = go.Surface(x=x1, y=x2, z=z, opacity = 0.9)
f = x1+x2 # target function
# x1 = np.linspace(-4,4)
# x2 = np.linspace(-2,2)
# f = np.zeros((len(x1), len(x2)))
# for i in range(len(x1)):
# for j in range(len(x2)):
# f[i][j] = x1[i]+ x2[j]
target_function = go.Surface(x = x1, y = x2, z=f, opacity = 0.8)
data = [budget_set, target_function]
layout = go.Layout(
title='Пример 1',
scene=dict(
xaxis=dict(
title = 'x1',
gridcolor='rgb(255, 255, 255)',
zerolinecolor='rgb(255, 255, 255)',
showbackground=True,
backgroundcolor='rgb(230, 230,230)'
),
yaxis=dict(
title = 'x2',
gridcolor='rgb(255, 255, 255)',
zerolinecolor='rgb(255, 255, 255)',
showbackground=True,
backgroundcolor='rgb(230, 230,230)'
),
zaxis=dict(
title = 'f(x1, x2)',
gridcolor='rgb(255, 255, 255)',
zerolinecolor='rgb(255, 255, 255)',
showbackground=True,
backgroundcolor='rgb(230, 230,230)'
)
)
)
fig = go.Figure(data=data, layout=layout)
plotly.offline.iplot(fig)
Для столь простого примера экстремумы ясны сразу, тем не менее, воспользуемся стандартной геометрической процедурой поиска:
import numpy as np
from matplotlib import pyplot as plt
%matplotlib inline
r = 1 # radius
phi = np.linspace(0, 2*np.pi, 240) # angle
r, phi = np.meshgrid(r, phi) # computational grid
x1 = 2 * r * np.cos(phi) # parametrization
x2 = r * np.sin(phi)
plt.plot(x1,x2)
plt.plot(x1, -2-x1, label='-2')
plt.plot(x1, -1-x1, label='-1')
plt.plot(x1, -x1, label='0')
plt.plot(x1, 1-x1, label='1')
plt.plot(x1, 2-x1, label='2')
plt.ylim([-2,2])
plt.legend()
<matplotlib.legend.Legend at 0x1bf4bd436a0>
Ясно, что максимум и минимум достигается на границе целевого множества, т.е. на пересечении прямой $x_2 = c - x_1$ и эллипса $x_1^2 + 4x_2^2 = 4$. Решение задачи, доступное любому школьнику состоит в том, чтобы решить систему уравнений $$ \begin{cases} x_2 = c - x_1, \\ x_1^2 + 4x_2^2 = 4. \end{cases} $$
При максимальном и минимальном допустимом значении $c$.
$$ \begin{cases} x_2 = c - x_1, \\ 5x_1^2 - 8c x_1 + 4c^2 - 4 = 0 \end{cases} $$$$D = 64 c^2 - 80 c^2 + 80 = 80 - 16c^2$$$$x_1 = \dfrac{8c \pm \sqrt{80 - 16c^2}}{10}$$Очевидно, что $c^2 \le 5 \rightarrow c_{min} = - \sqrt{5}, c_{max} = \sqrt{5}$
Значит, $x_1 = \dfrac{4}{5}c, \; x_2 = \dfrac{1}{5}c$, тогда $\left(\dfrac{4}{\sqrt{5}}, \dfrac{1}{\sqrt{5}}\right)$ - $max$, $\left(-\dfrac{4}{\sqrt{5}}, -\dfrac{1}{\sqrt{5}}\right)$ - $min$
В данной задаче супремум совпадает с точкой максимума, а инфимум с точкой минимума. Действительно:
plt.plot(x1,x2)
plt.plot(x1, np.sqrt(5)-x1, label='sqrt(5)')
plt.plot(x1, -np.sqrt(5)-x1, label='-sqrt(5)')
plt.ylim([-2,2])
(-2, 2)
$\text{extr}\left(\left|x_1\right|^\lambda + 2 \left|x_2\right|^\lambda \right)$ при условии $x_1^2 + 4x_2^2 \le 4, \;\; \lambda \neq 0$
Решение:
import plotly
import plotly.plotly as py
import plotly.graph_objs as go
from plotly import tools
plotly.offline.init_notebook_mode(connected=True)
import numpy as np
precise = 40
r = np.linspace(0,1,precise) # radius
phi = np.linspace(0, 2*np.pi, precise) # angle
r, phi = np.meshgrid(r, phi) # computational grid
x1 = 2 * r * np.cos(phi) # parametrization
x2 = r * np.sin(phi)
z = np.zeros((precise,precise))
budget_set = go.Surface(x=x1, y=x2, z=z, opacity = 0.9)
lam = [0.5, 1, 2]
fig = tools.make_subplots(rows=1, cols=len(lam),specs=[[{'is_3d': True} for i in range(len(lam))]])
f_ = {}
for lamb in lam:
f_[lamb] = np.abs(x1)**lamb + 2*np.abs(x2)**lamb # target function
target_function = {}
data = [budget_set]
fig['layout'].update(title='lambda > 0')
scene = dict(
xaxis=dict(
title = 'x1',
gridcolor='rgb(255, 255, 255)',
zerolinecolor='rgb(255, 255, 255)',
showbackground=True,
backgroundcolor='rgb(230, 230,230)'
),
yaxis=dict(
title = 'x2',
gridcolor='rgb(255, 255, 255)',
zerolinecolor='rgb(255, 255, 255)',
showbackground=True,
backgroundcolor='rgb(230, 230,230)'
),
zaxis=dict(
title = 'f(x1, x2)',
gridcolor='rgb(255, 255, 255)',
zerolinecolor='rgb(255, 255, 255)',
showbackground=True,
backgroundcolor='rgb(230, 230,230)'
)
)
i = 1
for lamb in lam:
target_function[lamb] = go.Surface(x = x1, y = x2, z=f_[lamb], opacity = 0.8, name = 'lambda = '+str(lamb))
data.append(target_function[lamb])
fig.append_trace(budget_set, 1, i)
fig.append_trace(target_function[lamb], 1, i)
fig['layout']['scene'+str(i)].update(scene)
i += 1
plotly.offline.iplot(fig)
This is the format of your plot grid: [ (1,1) scene1 ] [ (1,2) scene2 ] [ (1,3) scene3 ]
По хорошему, задача решается абсолютно так же - рисованием линий уровней $f(x_1, x_2) = const$ и приравниванием уравнений касательных. Однако, в этой задаче ясно, что $(0, 0)$ - точка $min$ (она же инфимум этой задачи). Что же касается максимумов, давайте посмотрим:
$$ \begin{cases} x_1^2 + 4x_2^2 = 4, \\ \left|x_1\right|^\lambda + 2 \left|x_2\right|^\lambda = c \end{cases} $$В силу симметрии, можем рассмотреть лишь положительные значения $x_1, x_2$:
$$ \begin{cases} x_1^2 + 4x_2^2 = 4, \\ x_1^\lambda + 2 x_2^\lambda = c \end{cases} $$Вообще говоря, надо решить эту систему для всех $\lambda$ и максимального значения $c$, т.е. можно выразить $x_2 = x_2(x_1)$ и приравнять производные по $x_1$ первого и второго уравнений (условие касания). Особый интерес вызывает поведение решений при $\lambda \in (1,2)$, при всех остальных положительных значениях решения совпадают с теми, что указаны на рисунке выше. Читателю предлагается придумать способ найти аналитическое решение в этом случае.
В случае же $\lambda <0$ точка $(0,0)$ является супремумом целевой функции на заданном множестве. И эту точку стоит включить в ответ. Графики ниже.
import plotly
import plotly.plotly as py
import plotly.graph_objs as go
from plotly import tools
plotly.offline.init_notebook_mode(connected=True)
import numpy as np
precise = 40
r = np.linspace(0,1,precise) # radius
phi = np.linspace(0, 2*np.pi, precise) # angle
r, phi = np.meshgrid(r, phi) # computational grid
x1 = 2 * r * np.cos(phi) # parametrization
x2 = r * np.sin(phi)
z = np.zeros((precise,precise))
budget_set = go.Surface(x=x1, y=x2, z=z, opacity = 0.9)
lam = [-0.5, -1, -2]
fig = tools.make_subplots(rows=1, cols=len(lam),specs=[[{'is_3d': True} for i in range(len(lam))]])
f_ = {}
for lamb in lam:
f_[lamb] = np.abs(x1)**lamb + 2*np.abs(x2)**lamb # target function
target_function = {}
data = [budget_set]
fig['layout'].update(title='lambda < 0')
scene = dict(
xaxis=dict(
title = 'x1',
gridcolor='rgb(255, 255, 255)',
zerolinecolor='rgb(255, 255, 255)',
showbackground=True,
backgroundcolor='rgb(230, 230,230)'
),
yaxis=dict(
title = 'x2',
gridcolor='rgb(255, 255, 255)',
zerolinecolor='rgb(255, 255, 255)',
showbackground=True,
backgroundcolor='rgb(230, 230,230)'
),
zaxis=dict(
title = 'f(x1, x2)',
gridcolor='rgb(255, 255, 255)',
zerolinecolor='rgb(255, 255, 255)',
showbackground=True,
backgroundcolor='rgb(230, 230,230)',
range = [0,20]
)
)
i = 1
for lamb in lam:
target_function[lamb] = go.Surface(x = x1, y = x2, z=f_[lamb], opacity = 0.8, name = 'lambda = '+str(lamb))
data.append(target_function[lamb])
fig.append_trace(budget_set, 1, i)
fig.append_trace(target_function[lamb], 1, i)
fig['layout']['scene'+str(i)].update(scene)
i += 1
plotly.offline.iplot(fig)
This is the format of your plot grid: [ (1,1) scene1 ] [ (1,2) scene2 ] [ (1,3) scene3 ]
Используя геометрические интерпретации, решить следующие экстремальные задачи:
$\text{extr}\left(\left|x_1\right|^\lambda + 2 \left|x_2\right|^\lambda \right)$ при условии $x_1^2 + 4x_2^2 = 4, \;\; \lambda \neq 0$
$\text{extr}\left(x_1^2 + 4x_2^2\right)$ при условии $\left|x_1\right|^\lambda + 2 \left|x_2\right|^\lambda \le 1, \;\; \lambda \neq 0$
$\text{extr}\left(x_1^2 + 4x_2^2\right)$ при условии $\left|x_1\right|^\lambda + 2 \left|x_2\right|^\lambda = 1, \;\; \lambda \neq 0$
В качестве решения необходимо предоставить либо:
jupyter notebook с построенными графиками целевой функции и бюджетного множества, описывающие различные параметры $\lambda$. Для построения графиков можно использовать код указанный в этом семинаре, но будет проще рабоать с библиотекой matplotlibПлюсом будут отмечены те решения, что рассмотрят $\lambda \in R \backslash \{0\}$